//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,2,1]
//输出：true
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,2]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围[1, 10⁵] 内 
// 0 <= Node.val <= 9 
// 
//
// 
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
//
// Related Topics 栈 递归 链表 双指针 👍 1642 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

import java.util.Stack;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode h1) {
        if (h1 == null || h1.next == null) {
            return true;
        }
        ListNode p1 = h1; 	// 慢指针，中间点
        ListNode p2 = h1; 	// 快指针
        ListNode n1 = null;	// 新头
        ListNode o1 = h1;	// 旧头
        // 快慢指针找中间点
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;

            // 反转前半部分
            o1.next = n1;
            n1 = o1;
            o1 = p1;
        }
        if (p2 != null) { // 节点数为奇数
            p1 = p1.next;
        }
        // 同步比较新头和后半部分
        while (n1 != null) {
            if (n1.val != p1.val) {
                return false;
            }
            p1 = p1.next;
            n1 = n1.next;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
